package F.树;

public class _110_平衡二叉树 {

    /**
     * 判断左右子树的高度是不是相差小于等于1
     * 自解：递归
     * 函数作用 判断root左右子树的高度差<=1
     * 终止条件 左右子树均为0
     * 依次递归左子树和柚子树
     * 难点：怎么判断高度呢？？
     * -----仿照题解代码  自顶向下遍历==当作前序遍历
     * 重复计算了很多height
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }


        return Math.abs(height(root.right)-height(root.left))<=1 && isBalanced(root.left) && isBalanced(root.right);

    }

    //另一个递归秋高度 函数作用计算结点高度
    //本结点高度就是 左右结点高度最大值加1
    public int height(TreeNode root){
        if (root == null){
            return 0;
        }

        return Math.max(height(root.right),height(root.left))+1;

    }

    /**
     * 优化：因为上面的方法 重复计算了很多次height
     * 所以采用自底向上的方法 类似于后序遍历
     *
     * 如果子树是平衡的 就返回子树高度 如果不是就返回-1
     * 因此用height函数返回值是否>=0判断结果
     */

    public boolean isBalanced1(TreeNode root) {
        return height1(root)>=0;

    }

    public int height1(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = height1(root.left);
        if (leftHeight==-1){
            return -1;
        }
        int rightHeight = height1(root.right);
        if (rightHeight == -1 || Math.abs(leftHeight-rightHeight)>1){
            return -1;

        }

        return Math.max(leftHeight,rightHeight)+1;

    }




}
